Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Pairs of Songs With Total Durations Divisible by 60

Problem Statement

You are given a list of positive integer times, where times[i] represents the duration of ith song in seconds.

Return the number of unique song pairs for which their total duration in seconds is multiple of 60. In other words, find the number of indices i, j such that i < j with (times[i] + times[j]) % 60 == 0.

Examples

Example 1:

  • Input: times = [30, 20, 150, 100, 40, 110]
  • Expected Output: 3
  • Justification: The pairs of songs that can form a total duration divisible by 60 are (30, 150), (20, 100), and (20, 40). Each of these pairs sums up to a multiple of 60, hence the expected output is 3.

Example 2:

  • Input: times = [120, 180, 60]
  • Expected Output: 3
  • Justification: The sum of (120, 180), (120, 60), and (180, 60) are divisible by 60. So, the expected output is 3.

Example 3:

  • Input: times = [15, 225, 90, 60]
  • Expected Output: 1
  • Justification: The only pair of songs that can form a total duration divisible by 60 is (15, 225).

Solution

To solve this problem, we'll use a hash table to keep track of the frequencies of song durations modulo 60. The rationale behind this approach is that if the sum of two numbers is divisible by 60, then the sum of their remainders when divided by 60 should also be 0. This method is effective because it allows us to handle each duration independently and just focus on its contribution towards forming a valid pair, significantly simplifying the problem.

First, we iterate through the list of song durations, calculating each song's remainder when divided by 60 and updating the frequency of these remainders in our hash table. Then, for each duration, we look for complementary durations that can form a valid pair with it. This two-step process efficiently identifies all possible pairs without the need for direct comparison of each song duration with every other, thereby reducing computational complexity and increasing algorithm efficiency.

Step-by-Step Algorithm

  1. Initialize a Frequency Array: Create an array named remainderFrequency with a size of 60 to store the frequency of the remainders when each song duration is divided by 60. This array is initialized with all elements set to 0.

  2. Populate the Frequency Array: Iterate through each element in the input array times. For each song duration t in times, calculate the remainder of t divided by 60. Increment the value at the index of this remainder in the remainderFrequency array by 1. This step counts how many songs have durations that leave the same remainder when divided by 60.

  3. Initialize a Count Variable: Initialize a variable count to 0. This variable will keep track of the total number of valid pairs of songs found.

  4. Calculate Pairs for Special Cases: Calculate the number of valid pairs for songs that leave a remainder of 0 and for songs that leave a remainder of 30 when their durations are divided by 60. This is done because these remainders pair with themselves. Use the formula remainderFrequency[i] * (remainderFrequency[i] - 1) / 2 for i = 0 and i = 30, and add the results to count.

  5. Calculate Pairs for Other Remainders: Iterate from i = 1 to i = 29. For each i, find the product of the frequency of songs with remainder i and the frequency of songs with remainder 60 - i. Add this product to count. This step finds and counts all valid pairs of songs where the sum of their durations' remainders equals 60.

  6. Return the Total Count: After iterating through the remainderFrequency array and calculating all possible pairs, return the value of count. This value represents the total number of pairs of songs where the sum of their durations is divisible by 60.

Algorithm Walkthrough

Image
  1. Initialize remainderFrequency Array: Create an array of size 60, initialized with zeros.

  2. Populate the Frequency Array:

    • For 30, calculate 30 % 60 = 30. Increment remainderFrequency[30] to 1.
    • For 20, calculate 20 % 60 = 20. Increment remainderFrequency[20] to 1.
    • For 150, calculate 150 % 60 = 30. Increment remainderFrequency[30] to 2.
    • For 100, calculate 100 % 60 = 40. Increment remainderFrequency[40] to 1.
    • For 40, calculate 40 % 60 = 40. Increment remainderFrequency[40] to 2.
    • For 110, calculate 110 % 60 = 50. Increment remainderFrequency[50] to 1.
    • The final hashmap is {20: 1, 30: 2, 40: 2, 50: 1}.
  3. Initialize count Variable: Set count to 0.

  4. Calculate Pairs for Special Cases:

    • For i = 0, there are no songs with a remainder of 0, so count remains 0.
    • For i = 30, use the formula 2 * (2 - 1) / 2 = 1. Increment count by 1.
  5. Calculate Pairs for Other Remainders:

    • For i = 1 to 29, calculate pairs.
    • For i = 20, add remainderFrequency[20] * remainderFrequency[40] = 1 * 2 = 2 in the count. count = 1 + 2 = 3
  6. Return the Total Count: The final count is 3, indicating there are 3 valid pairs of songs where the sum of their durations is divisible by 60.

Code

Java

. . . .

Complexity Analysis

Time Complexity

  • : The algorithm iterates through the input array times once to populate the remainderFrequency array, where n is the number of elements in times. This operation takes linear time. Afterward, it iterates through the remainderFrequency array up to 30 times to calculate the number of valid pairs. Since this second iteration is a constant operation (does not depend on the input size n), the overall time complexity remains .

Space Complexity

  • : The space complexity is constant because the algorithm uses a fixed-size array remainderFrequency of size 60, regardless of the input size. Other variables used in the algorithm do not significantly affect the space usage.
Pairs of Songs With Total Durations Divisible by 60 (medium)
Search a 2D Matrix II (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity